class Solution(object):
    def hasPath(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        m = len(maze)
        n = len(maze[0])
        used = [[0 for _ in range(n)] for _ in range(m)]
        used[start[0]][start[1]] = 1

        def search(point):
            if point == destination:
                return True
            x = point[0]
            y = point[1]
            flag = False
            if x > 0:
                index = x
                while index - 1 >= 0 and maze[index - 1][y] == 0:
                    index -= 1
                if index != x and used[index][y] == 0:
                    used[index][y] = 1
                    flag = flag or search([index, y])
            if not flag and x < m:
                index = x
                while index + 1 < m and maze[index + 1][y] == 0:
                    index += 1
                if index != x and used[index][y] == 0:
                    used[index][y] = 1
                    flag = flag or search([index, y])
            if not flag and y > 0:
                index = y
                while index - 1 >= 0 and maze[x][index - 1] == 0:
                    index -= 1
                if index != y and used[x][index] == 0:
                    used[x][index] = 1
                    flag = flag or search([x, index])
            if not flag and y < n:
                index = y
                while index + 1 < n and maze[x][index + 1] == 0:
                    index += 1
                if index != y and used[x][index] == 0:
                    used[x][index] = 1
                    flag = flag or search([x, index])
            return flag

        return search(start)


data = Solution()
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [4, 3]
destination = [0, 1]
print(data.hasPath(maze, start, destination))
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [0, 4]
destination = [3, 2]
print(data.hasPath(maze, start, destination))
maze = [[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [1, 1, 0, 1, 1], [0, 0, 0, 0, 0]]
start = [0, 4]
destination = [4, 4]
print(data.hasPath(maze, start, destination))
